1. Field of the Invention
The present invention relates generally to the multiplications of finite field elements, in applications where error correction capabilities are required, and more particularly to bit-serial multipliers used to perform multiplications of field elements over Galois Field GF (2.sup.m).
2. State of the Art
Finite (or Galois) fields can be applied to many areas of electrical system designs including error correcting codes, switching theory, and digital signal processing. In general, the application of Galois Fields in these areas (and particularly multiplication in Galois Fields) is one in which a derived mathematical algorithm in some Galois Field is implemented using logic elements to obtain-a desired function or result from the system. A multiplication operation performed in Galois Fields is implemented using logic elements referred to as multipliers, which perform logical operations on the input data to generate output data representing the result of the multiplication of the input data elements.
One example of a multiplier for finite field elements is a fully combinational parallel logic multiplier as described in "Systolic Multipliers for Finite Fields GF(2.sup.m)," by C. S. Yeh, Irving S. Reed, and T. K. Troung, IEEE Transactions on Computers, Vol. C-33, No. 4, April 1984 and incorporated herein. A fully combinational logic design does not include any sequential logic and hence must perform all intermediate steps. As a result, this type of multiplier includes a significant number of logic gates to implement it. Two examples of a bit serial multiplier are shown in "Efficient Bit-Serial Multiplication and the Discrete-Time Wiener-Hopf Equation Over Finite Fields," by M. Kasahara, M. Morii, and D. L. Whiting, IEEE Transactions on Information Theory, Vol. 35, No. 6, pp. 1177-1183, November 1989, and in "Encoder Using Berlekamp's Bit-Serial Multiplier Algorithm," by L. Deutsch, I. S. Reed, T. K. Troung, K. Wang, C. Yeh, IEEE Transactions on Computers, Vol. C-33, No. 10, pp. 906-911, October 1984, both incorporated herein. Bit serial multiplier designs reduce the number of required logic gates by reusing gates in a reiterative manner and pipelining to perform the multiplication operation.
As the bandwidth requirement of communication devices increases and hence the number of elements involved in the multiplication operations, there is a need for faster multiplication operations and multipliers which use minimum silicon area. A multiplier that is designed with fully combinational logic, uses large numbers of logic gates to perform a quick parallel multiplication. However, the speed at which the parallel multiplier described in "Systolic Multipliers for Finite Fields GF(2.sup.m)" performs the multiplication is at the expense of large silicon area consumption. Bit-serial multiplier designs minimize silicon area use however, at the expense of reduced performance. The disadvantages associated with both of these schemes are that the performance vs. silicon area is not optimized to yield the best design solution.
The goal of the present invention is to implement a 2.sup.n -bit serial multiplier design that performs fast multiplications of two arbitrary field elements .lambda. and .psi. over the Galois Field, GF (2.sup.m) using minimal silicon area.